//这里开始记录图的笔记
//这里先学如何表示图
//用0到v-1的数来表示顶点
//可以用邻接矩阵表示整个图
//最广泛使用的一种是邻接表,这种方法的时间和空间消耗都和边数成正比
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.*;
public class Graph {
    //创建一个有v个点的空图
    private final int V;
    private int E;
    private Bag<Integer>[] adj;
    public Graph(int v)
    {
       this.V=v;
       this.E=0;
       adj=(Bag<Integer>[]) new Bag[V];
       for(int i=0;i<V;i++)
       {
        adj[i]=new Bag<Integer>();
       }
    }

    //从输入流中创建图
    public Graph(In in)
    {
      if (in == null) throw new IllegalArgumentException("argument is null");
        try {
            this.V = in.readInt();
            if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be non-negative");
            adj = (Bag<Integer>[]) new Bag[V];
            for (int v = 0; v < V; v++) {
                adj[v] = new Bag<Integer>();
            }
            int E = in.readInt();
            if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be non-negative");
            for (int i = 0; i < E; i++) {
                int v = in.readInt();
                int w = in.readInt();
                addEdge(v, w);
            }
        }
        catch (NoSuchElementException e) {
            throw new IllegalArgumentException("invalid input format in Graph constructor", e);
        }
    }

    //添加 v-w 边
    public void addEdge(int v,int w)
    {
        adj[v].add(w);
        adj[w].add(v);
        this.E++;
    }

    //返回一个点的相邻点
    public Iterable<Integer> adj(int v)
    {
       return adj[v];
    }

    //返回点的数量
    public int V()
    {
      return V;
    }

    //返回边的数量
    public int E()
    {
       return E;
    }

    public String toString()
    {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges " + "\n");
        for (int v = 0; v < V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
    public static void main(String[] args) throws Exception {
        In in = new In("input.txt");
        Graph g=new Graph(in);
        Path_BFS dfs=new Path_BFS(g, 0);
        for(Integer dot:dfs.PathTo(3))
        {
            System.out.printf("%d ", dot);
        }
        System.out.printf("\n");
        System.out.println(g.toString());
    }
}
